1. Field of the Invention
The present invention relates to a content addressable memory (CAM) device which can be used as a binary CAM device, and also as a ternary CAM device in which ternary data, including binary data and xe2x80x9cX (don""t care),xe2x80x9d can be specified, and to structure methods therefor.
2. Description of the Related Art
As Internet technologies have advanced in these years, it has been demanded that network relay apparatuses, such as switching hubs and routers, operate at high speeds with high-level functions. To satisfy such a demand, these relay apparatuses have used CAM devices for processing, such as address filtering and packet classification, in many cases.
CAM devices have also been used in layers 2, 3, and 4 of the network Open Systems Interconnection (OSI) model in many cases. In these cases, the length of search key data varies from 32 bits to more than 256 bits; conventionally binary CAM devices, which can have only xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d as data, are sufficient in some cases; and ternary CAM devices, which can have xe2x80x9c0,xe2x80x9d xe2x80x9c1,xe2x80x9d and xe2x80x9cX (don""t care)xe2x80x9d as data, are required in other cases.
Conventional binary CAM and ternary CAM devices will be described below.
FIG. 10 is a structural block diagram of a conventional CAM device.
The CAM device 90 shown in FIG. 10 is provided with a m-bit by n-word CAM array 92; an input-and-output (I/O) circuit 94 for driving write-in data, read-out data, and search data; a decoder 96 for decoding an address signal ADR to specify a CAM word corresponding thereto; and a priority encoder 98 for encoding the match lines word for which matching has been detected, according to a priority and for outputting the addresses of the CAM words having the match lines.
In the CAM device 90, write-in data input from the outside by the I/O circuit 94 is written into a CAM word selected by the decoder 96 according to an address signal ADR, as storage data. Storage data is read from a CAM word selected by the decoder 96 and output to the outside by the I/O circuit 94 as read-out data.
Search data input from the outside is driven by the I/O circuit 94, and a search operation is performed between the search data and storage data for all CAM words. The result of search for each CAM word is input to the priority encoder 98 through a match line, and the memory address of a CAM word for which matching has been detected is sequentially output as a highest hit address (HHA), according to a predetermined priority.
A binary CAM device has binary CAM cells, and a ternary CAM device has ternary CAM cells.
FIG. 11 is a circuit diagram of a binary CAM cell used in a conventional CAM device. The binary CAM cell 100 shown in FIG. 11 is formed of a data storage portion 102 for storing one-bit data, xe2x80x9c0xe2x80x9d or xe2x80x9c1,xe2x80x9d and a match detector 104 for comparing data stored in the data storage portion 102 with search data input from the outside of the CAM device and for outputting a matching-detection result.
The data storage portion 102 is formed of a static RAM (SRAM) conventionally known to the public, and includes two inverters 46a and 46b and two n-type MOS transistors (NMOSS) 48a and 48b. In the two inverters 46a and 46b, the output terminal, of each of them is connected to the input terminal of the other. The NMOS 48a is connected between the input terminal of the inverter 46a and a bit line BL, and the NMOS 48b is connected between the input terminal of the inverter 46b and a bit bar line /BL. The gates of the two NMOSs are connected in common to a word line WL.
The match detector 104 is formed of four NMOSs 50a, 50b, 52a, and 52b. The NMOSs 50a and 52a are connected in series between a match line ML and the ground, the gate of the NMOS 50a is connected to the output terminal (D) of the inverter 46b, and the gate of the NMOS 52a is connected to the bit line BL. The NMOSs 50b and 52b are connected in series between the match line ML and the ground, the gate of the NMOS 50b is connected to the output terminal (/D) of the inverter 46a, and the gate of the NMOS 52b is connected to the bit bar line /BL.
In the binary CAM device having the binary CAM cell 100, searching is performed in a way in which the bit line BL and the bit bar line /BL are set to a low level to turn off the NMOSs 52a and 52b, the match line ML is pre-charged to a power potential, and then, search data is driven to the bit bar line /BL and search data bar is driven to the bit line BL.
When storage data matches the search data, since the NMOS 52a or 52b connected in series to whichever is on according to the storage data, of the NMOSs 50a and 50b becomes off, the match line ML maintains a pre-charge state. On the other hand, if no matching is found, since the NMOS 52a or 52b corresponding to whichever is on, of the NMOSs 50a and 50b becomes on, the match line ML is discharged through whichever pair is both on, of the NMOSs 50a and 52a, and the NMOSs 50b and 52b. 
FIG. 12 is a structural circuit diagram of a ternary CAM cell used in a conventional CAM. The ternary CAM cell 106 is formed of a data storage portion 102 having the same structure as in the above-described binary CAM cell 100, a mask-data storage portion 108 for storing data which determines whether to mask matching detection between storage data stored in the data storage portion 102 and search data, and a match detector 110 for comparing the storage data stored in the data storage portion 102 with the search data when masking is not performed by the mask-data storage portion 108 and for outputting a matching-detection result.
The mask-data storage portion 108 is formed of a static RAM (SRAM) in the same way as for the data storage section 102, and includes two inverters 112a and 112b and two NMOSs 114a and 114b. 
The match detector 110 has a NMOS 116 in addition to the components of the match detector 104 of the binary CAM cell 100 shown in FIG. 11. The NMOS 116 is connected between a match line ML and the drains of the NMOSs 50a and 50b, and its gate is connected to the output terminal (/M) of the inverter 112a of the mask-data storage portion 108.
A search operation in the ternary CAM device having the ternary CAM cell 106 is performed in a way in which, when the mask-data storage portion 108 stores xe2x80x9c0xe2x80x9d as mask data M (M=0, /M=1), since the NMOS 116 in the match detector 110 is turned on, the ternary CAM device performs the same function as the binary CAM device having the above-described binary CAM cell 100. On the other hand, when the mask-data storage portion 108 stores xe2x80x9c1xe2x80x9d as mask data M (M=1, /M =0), since the NMOS 116 is turned off, the match line ML has a high level irrespective of the state of the storage data (D), namely, always maintains a match state.
In this way, the CAM device having the ternary CAM cell 106 allows the search function to be masked by independently specifying a xe2x80x9cdon""t carexe2x80x9d for the CAM cell of each bit constituting each word. This function is called a local mask. In contrast, there has been known to the public a CAM device having a function for masking a search function for the same-position bits of all CAM words by applying xe2x80x9c0xe2x80x9d to the bit line BL and the bit bar line /BL. This function is called a global mask.
Conventional binary CAM devices having the above structure cannot be used as ternary CAM devices because a xe2x80x9cdon""t carexe2x80x9d cannot be specified as storage data itself in the binary CAM devices.
When conventional ternary CAM devices are used as binary CAM devices, all mask data used for specifying a xe2x80x9cdon""t carexe2x80x9d needs to be set to a no-mask state. In this case, however, since mask bits unnecessary for binary CAM devices are provided, an increase in bit cost occurs. In addition, a data writing operation needs to be performed twice, once for the data storage portion and once for the mask-data storage portion, in the ternary CAM devices whereas a data writing operation is required only once in binary CAM devices.
It is an object of the present invention to solve the problems caused by the conventional technology and to provide a CAM device which can be used as binary CAM device or a ternary CAM device, and which does not use storage bits wastefully even if the CAM device is used as a binary CAM device, and a structure method therefor.
To achieve the foregoing object, the present invention provides a content addressable memory (CAM) device configured with binary CAM cells capable of holding binary data xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d, and capable of being used either as a binary CAM device with the binary CAM cells being used as binary CAM cells or as a ternary CAM device with the binary CAM cells being used as ternary CAM cells capable of holding ternary data in a way in which, in each pair of two bits of the binary CAM cells, three states, xe2x80x9c0,xe2x80x9d xe2x80x9c1,xe2x80x9d and xe2x80x9cX (don""t care)xe2x80x9d are assigned to four states, xe2x80x9c00,xe2x80x9d xe2x80x9c01,xe2x80x9d xe2x80x9c10,xe2x80x9d and xe2x80x9c11,xe2x80x9d expressed by two-bit data stored in the pair.
The each pair of binary CAM cells may be included in two different CAM words, or included in one CAM word.
It is preferred that, during search, a pair of search bit lines used for one binary CAM cell of the each pair of the binary CAM cells and a pair of search bit lines used for the other binary CAM cell be separately controlled.
It is also preferred that, when the CAM device is used as a ternary CAM device, data conversion processing be applied to storage data, mask data (for local mask), and search data between external data (logical data) and internal data (physical data).
The present invention also provides a CAM device including a CAM array including a plurality of CAM words each formed of binary CAM cells; and binary/ternary setting means for making a setting of a case in which the binary CAM cells are used as binary CAM cells or a setting of a case in which each pair of two bits of the binary CAM cells is used as a ternary cell. It is preferred that the CAM device include a logical-data/physical-data conversion circuit for converting logical data input from the outside to physical data used in the inside of the CAM device, and vice versa, according to the setting of the binary/ternary setting means.
The present invention further provides a structure method for a CAM device configured with binary CAM cells capable of holding binary data xe2x80x9c0xe2x80x9d and xe2x80x9c1,xe2x80x9d wherein, in each pair of two bits of the binary CAM cells, three states, xe2x80x9c0,xe2x80x9d xe2x80x9c1,xe2x80x9d and xe2x80x9cX (don""t care)xe2x80x9d are assigned to four states, xe2x80x9c00,xe2x80x9d xe2x80x9c01,xe2x80x9d xe2x80x9c10,xe2x80x9d and xe2x80x9c11,xe2x80x9d expressed by two-bit data stored in the pair to implement the function of a ternary CAM cell capable of holding ternary data.